#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef double db;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); }
	return x*f;
}
const int MAXN=5e4+10;
int n,pri[MAXN],tot,mu[MAXN],sum[MAXN];
bool ispri[MAXN];
void cal_prime_mu()
{
	mu[1]=1;
	for(int i=2;i<=50000;++i)
	{
		if(!ispri[i])
		{
			mu[i]=-1;
			pri[++tot]=i;
		}
		for(int j=1;i*pri[j]<=50000&&j<=tot;++j)
		{
			ispri[i*pri[j]]=true;
			if(i%pri[j]==0)
			{
				mu[i*pri[j]]=0;
				break;
			}
			mu[i*pri[j]]=-mu[i];
		}
	}
	for(int i=1;i<=50000;++i)
		sum[i]=sum[i-1]+mu[i];
}
int solve(int n,int m)
{
	if(n>m)swap(n,m);
	int ret=0;
	for(int l=1,r;l<=n;l=r+1)
	{
		r=min(n/(n/l),m/(m/l));
		ret+=(sum[r]-sum[l-1])*(n/l)*(m/l);
	}
	return ret;
}
int main()
{
	cal_prime_mu();
	n=read();
	while(n--)
	{
		int a=read(),b=read(),c=read(),d=read(),k=read();
		--a;--c;a/=k;b/=k;c/=k;d/=k;
		printf("%d\n",solve(b,d)+solve(a,c)-solve(a,d)-solve(b,c));
	}
	return 0;
}
